// 邻接矩阵存储无向图

#include <stdio.h>
#include <stdlib.h>

#define INFINITY 100
#define MAX_VEX_NUM 20
#define OK 1
#define ERROR 0

typedef int Status;
typedef char VertexType;   //顶点数据元素类型

typedef struct {
    VertexType vexs[MAX_VEX_NUM]; // 顶点数组
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];                  // 邻接矩阵
    int vexnum, arcnum;     // 图的顶点数n和弧(边)数 e
} MGraph; //图类型定义

VertexType *array = (VertexType *) malloc(sizeof(VertexType) * MAX_VEX_NUM); //深搜序列存在全局数组全局数组VertexType array[]
int count=0; // 用于标记已经存储了几个
int *visit = (int *) malloc(sizeof(int) * MAX_VEX_NUM); //定义标志数据，标记顶点是否被访问过

int LocateVex(MGraph G, VertexType v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == v)
            return i;
    }
    return -1;
}//求顶点v在图中的位置，若不存在返回-1，存在返回[0,n-1]

Status CreateUDN(MGraph &G) {
    scanf("%d%d", &G.vexnum, &G.arcnum);
    getchar();
    for (int i = 0; i < G.vexnum; i++)
        scanf("%c", &G.vexs[i]);
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = INFINITY;
    for (int i = 0; i < G.arcnum; i++) {
        getchar();
        VertexType a, b;
        int w;
        scanf("%c%c%d", &a, &b, &w);
        int k, j;
        k = LocateVex(G, a);
        j = LocateVex(G, b);
        if (k == -1 || j == -1)
            return ERROR;
        G.arcs[k][j] = w;
        G.arcs[j][k] = w;
    }
    return OK;
}//采用邻接矩阵法构造无向网

void degree(MGraph G, int Deg[]) {
    for (int i = 0; i < G.vexnum; i++) {
        int n = 0;
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != 0)
                n++;
        }
        Deg[i] = n;
    }
}//求各个顶点的度返回在数组Deg。

int firstadj(MGraph G, int v) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.arcs[v][i] == 1)
            return i;
    }
    return -1;
}//返回下标v顶点的第一个邻接顶点下标，若无邻接顶点则返回-1;

int nextadj(MGraph G, int v, int w) {
    for (int i = w + 1; i < G.vexnum; ++i) {
        if (G.arcs[v][i] == 1)
            return i;
    }
    return -1;
}//返回下标v顶点在下标w之后的下一个邻接顶点。不存在则返回-1;

void DFS(MGraph G, int v) {
    array[count++]=G.vexs[v];
    visit[v] = 1;
    for (int w = firstadj(G, v); w >= 0; w = nextadj(G, v, w)) {
        if (visit[w] == 0)
            DFS(G, w);
    }
}//在图G中以下标v的顶点为起点开始做深度优先遍历顶点输出

void DFSTraver(MGraph G) {
    int i;
    for (i = 0; i < G.vexnum; i++) {
        visit[i] = 0;
    }
    for (i = 0; i < G.vexnum; i++) {
        if (!visit[i]) DFS(G, i);
    }
}//对图G进行深度优先搜索，